Binary heap data structure - Has a method heap-size that gives you the number of element from the heap that are in the array, so that
Given the root of a tree is , and you are given the index of a node, you can calculate the indices of it’s parent, left child, and right child with the following code:
PARENT(i)
return floor(i/2)
LEFT(i)
return 2i
RIGHT(i)
return 2i + 1
Types of Heaps
There are two types of heaps but each type has a heap priority.
- Max-Heap - The heap will have a root that is the max number in the heap. The priority is that for every node other than the root
- HEAP-SORT uses the max-heap!
- Min-Heap - The heap will have a root that is the min number in the heap. The priority is that for every node other than the root
- Min-heaps area commonly used to implement priority queues.
Time Complexity
Height of a node - the longest simple downward path from the node to a leaf. The height of a tree is the height from the root node. A heap of n elements has a height of and basic operations on heaps run in time at most proportional to the height of the tree. Thus they take time.
- The MAX-HEAPIFY procedure, which runs in time, is the key to maintaining the max-heap property.
- The BUILD-MAX-HEAP procedure, which runs in linear time, produces a maxheap from an unordered input array.
- The HEAPSORT procedure, which runs in time, sorts an array in place.
- The procedures MAX-HEAP-INSERT, MAX-HEAP-EXTRACT-MAX, MAXHEAP-INCREASE-KEY, and MAX-HEAP-MAXIMUM allow the heap data structure to implement a priority queue. They run in time plus the time for mapping between objects being inserted into the priority queue and indices in the heap.